\documentclass[submission,narroweqnarray,inline]{ieee}
%\documentclass[%
%	%draft,
%	%submission,
%	%compressed,
%	final,
%	%
%	%technote,
%	%internal,
%	%submitted,
%	%inpress,
%	reprint,
%	%
%	%titlepage,
%	notitlepage,
%	%anonymous,
%	narroweqnarray,
%	inline
%	%twoside
%	]{ieee}

\usepackage{ieeefig}

\usepackage{listings}
\usepackage{pdfcolmk}
\usepackage{hyperref}
\usepackage{graphicx}
\usepackage{float}
\usepackage{subfig}
\usepackage{verbatim}
\usepackage{wrapfig}
\usepackage{moreverb}
\usepackage{fancyhdr}
\usepackage{xcolor}
% \usepackage[usenames,dvipsnames]{color}
\usepackage{color}
\usepackage{url}

\linespread{1.3} % 1.5 line spacing

\begin{document}
%----------------------------------------------------------------------
% Title Information, Abstract and Keywords
%----------------------------------------------------------------------
\title[Common Lisp]{%
       A History and Overview of the Common Lisp Programming Language}

% format author this way for journal articles.
\author[SHORT NAMES]{%
      Anthony Naddeo\member{Student Member}
      \authorinfo{%
      A. Computer Science Undergraduate Student,
      University of Maine, Orono ME 04469, USA,
      Phone: \mbox{(347) 210-0185}, email: \mbox{anthony.naddeo@gmail.com}}
  }

% format author this way for conference proceedings
\author[SHORT NAMES]{%
      Anthony Naddeo\member{Fellow}
      \authorinfo{%
      Computer Science Undergraduate Student\\
      University of Maine, Orono ME 04469, USA\\
      Phone: (347) 210-0185, email: anthony.naddeo@gmail.com}
  }

% specifiy the journal name
\journal{COS 301, 2011}

% Or, specify the conference place and date.
%\confplacedate{Ottawa, Canada, May 19--21, 1997}

% make the title
\maketitle        

%\tableofcontents

% do the abstract

\newpage

\begin{abstract}  
This paper will provide a brief overview of the history of the
Common Lisp programming language, as well as a brief overview of the 
language itself. We will discuss the syntax of the language to understand
how to start programming with it. This is not intended to be comprehensive by 
any means, merely introductory.
\end{abstract}


% do the keywords
\begin{keywords}
Lisp, programming language, history
\end{keywords}
\hyphenpenalty=10000

%config the listings settings
\lstset{language=Lisp,
identifierstyle=\ttfamily,
breaklines=true,
tabsize=2,
%title=\lstname,
basicstyle=\footnotesize,
keywordstyle=\color[rgb]{0,0.5,0},
commentstyle=\color{gray},
stringstyle=\color{red}}

\tableofcontents
\newpage
 
%----------------------------------------------------------------------
% SECTION I: Introduction
%----------------------------------------------------------------------
\section{Introduction}\label{sec:intro}
\PARstart The second oldest high level programming language that lent more to modern day programming paradigms than any other language has an incredibly rich history. The Lisp programming language gave birth to a plethora of dialects and spin-offs that are still in use years after their creation, some of which include Common Lisp, Scheme, and Clojure, though far more exist.

Each dialect has some unique features and no single one is necesarily better than any other all of the time. For example, Scheme reimplements Lisp with a minimalist design philosophy while the Clojure dialect targets the Java Virtual Machine\cite{clojure}. That being said, this paper will focus on Common Lisp because a large portion of the Lisp community has implicitly decided to settle upon it.

%----------------------------------------------------------------------
% SECTION II: History of (Common) Lisp
%---------------------------------------------------------------------- 
\section{History of Lisp}\label{sec:history}

Common Lisp's history starts sometime between 1956 and 1958 with the creation of the original Lisp specification by John McCarthy, an accomplished artificial intelligence researcher and professor\cite{mccarthy_prehistory}. At the time, programmers had only one choice when it came to high level languages: Fortran. While useful, artificial intelligence researchers and Mathematicians felt that there was a lot that Fortran could not do on the IBM 704 computeres of the time, like list processing\cite{mccarthy_prehistory}. The IBM 704 computers deserve mention here because McCarthy felt that IBM was in the best position to contribute to artificial intelligence reseaerch.

In 1958 McCarthy was hired at MIT to jump start their artificial intelligence project and started his implementation of Lisp. At this point, most of the early Lisp work was spent hand-compiling functions into assembly language to try and produce a Lisp environment, and ultimately a Lisp compiler\cite{mccarthy_implementation}.The programs that were to be hand compiled were written in a mathematical notation called M-expressions, though the final language would use S-expressions. The differences between the two notations are not very meaningful and the decision to use S-expressions was just a preference. The following is an example of each expression syntax.

\begin{lstlisting}
M-expression: +[2 3 4]
\end{lstlisting}

\begin{lstlisting}
S-expression: (+ 2 3 4)
\end{lstlisting}

These expressions both use the add function named ``+'' and take numbers as arguments.

Garbage collection would be added to the language as well. The motivation behind garbage collection came from a restriction of 36 bits on the word size of the IBM 704 that required either remodeling how McCarthy represented lists or having an automatic garbage collection system where storage is abandoned until all free storage is exhausted. McCarthy only decided to use garbage collection, he did not yet implement it\cite{mccarthy_implementation}.

Development on Lisp would soon be disrupted by a computer scientist from Dartmouth University named Steven Russel

%----------------------------------------------------------------------
\subsection{The First Lisp Interpreter}\label{sec:interpreter}

McCarthy specified a theoretical function \texttt{eval[e,a]} that evaluated a Lisp expression, \texttt{e}, with a list of assignments of variables, \texttt{a}, to show that Lisp could be used as a neater version of a Turing machine. This theoretical function was published and Steven Russel discovered that the \texttt{eval} function modeled by McCarthy to demonstrate Lisp's computational power could be used as an interpreter for the language. Russel coded the function and created the first Lisp interpreter.\cite{mccarthy_implementation}.

The unexpected creation of a Lisp interpreter caught McCarthy offguard. Having a working interpreter tended to freeze the Lisp specification and some features that deserved a little more thought made their way in. For example, Lisp was using S-expressions when the interpreter came out; McCarthy planned on switching to M-expressions but other parts of the language needed work and the newer programmers that were showing interest in Lisp preferred the S-expression syntax so the converesion took an indefinite backseat\cite{mccarthy_implementation}. 

%----------------------------------------------------------------------
\subsection{Common Lisp}\label{sec:commonlisp}

Over the next twenty five years Lisp was used in artificial intelligence research and general purpose programming, constantly being extended through the creation of new dialects. The numerous independent extentions lead to a fragmentation in the Lisp community. 

In 1984, Guy Steele specced a new Lisp dialect called Common Lisp that attempted to combine the efforts of existing dialects into a more complete, portable solution. The most influencial dialects on Common Lisp were MacLisp (developed for MIT's Mathematics and Computation program), ZetaLisp (descendant of MacLisp), Scheme (developed at MIT with Steele's help) and Interlisp (developed at BBN Technologies)\cite{common_lisp_intro}.

Steele intended for Common Lisp to satisfy a specific set of goals\cite{common_lisp_intro}.\\

\begin{itemize}
\item \textbf{Commonality.} Different implementation environments called for different inplementations. Common Lisp would serve as a core baseline that any platform specific modifications could be added to.
\item \textbf{Portability.} Building off of Commonality, any features that could not be implemented on all platforms were not included in Common Lisp. For example, type declaration is optional in Common Lisp because there was no portable, consistent, cross platform solution. When type declaration is used it is soley for optimization purposes, using Lisp functions like \texttt{declare} and \texttt{optimize}.
\item \textbf{Consistency.} Older Lisp dialects had compilers and interpreters that did not agree upon semantics. Common Lisp specifies that all code must be interpreted the same, whether it be by a compiler or an interpreter. 
\item \textbf{Expressiveness.} Using the power of hindisght, features from influencial dialects were cherry picked and added into Common Lisp.
\item \textbf{Compatibility.} Perhaps ``Backwards Compatibility'' would be more accurate. Common Lisp attempts to stay compatible with its parent dialects.
\item \textbf{Efficiency.} Designed to facilitate the compilation of efficient code. 
\item \textbf{Power.} Common Lisp is meant to be extensible.
\item \textbf{Stability.} Only changes that really need to be added will be added, and only after an appropriate amount of review.\\
\end{itemize}

The language specification was published in a book called ``Common Lisp the Language'' but was seen by Steele as incomplete\cite{common_lisp_preface}. In 1985 a meeting between Lisp users and implementers was held in Boston to discuss improvements to the Common Lisp specification. The interest and attendence made it clear that the specification had potential and needed some more formal support. This lead to the creation of the X3J13 committee, a subcommittee of the ANSI X3 committee\cite{common_lisp_preface}. X3's work would lead to an official ANSI Common Lisp specification in 1994 and a series of subsequent Common Lisp interpreteres and compilers. 

%----------------------------------------------------------------------
% SECTION III: Overview of Lisp
%----------------------------------------------------------------------
\section{Overview of Common Lisp}\label{sec:overview}

%Lisp was named after "List Procesing" for a reason\cite{mccarthy_prehistory}; everything in Lisp is a list waiting to be evaluated. Working to understand the syntax will help understand this core concept.

Lisp is an extremely unique and robust language, especially for its time. Many of the core ideas behind the language were firsts and carried over to modern day languages. Professor Paul Graham, author of "On Lisp: Advanced Techniques for Common Lisp (Perfect Paperback)", wrote about the traits that made Lisp different\cite{paul_graham}.\\

\begin{itemize}
\item \textbf{Conditionals.} The if-else statements we see in most languages today. Fortran had something like this at the time, but the implementaiton was based on the branch instruction, similar to using conditional jumps in Assembler.
\item \textbf{Functions as types.} Functions are now types and can be passed as parameters and stored in variables. Being able to pass functions as arguments to other functions enables recursion.
\item \textbf{Recursion.} Lisp was the first language to support recursion.
\item \textbf{New variable concept.} All variables are pointers with dynamic typing. 
\item \textbf{Garbage collection.} Automatic memory management.
\item \textbf{Programs composed of collections.} Each Lisp program is a series of collections, each of which returns one or more values.
\item \textbf{Language availability.} There is no real distinction between run-time and compile-time.\\
\end{itemize}

Many of these ideas are common today. For example, Java uses garbage collection, conditionals, recursion and pointer-only variables (though still typed). Python is dynaimcally typed, uses garbage collection, conditionals and recursion. These facts have fostered a sort of Lisp cult following. The following is a quote from Professor Philip Greenspun, a Lisp aficionado.\\

\textit{``Any sufficiently complicated C or Fortran program contains an ad-hoc, informally-specified bug-ridden slow implementation of half of Common Lisp.''}\\

This is referred to as Greenspun's Tenth Rule, and was intended to convey the idea that Lisp is so flexible and complete that it contains all of the tools necessary to write any computer program, whereas other languages need to implement some hackery to accomplish the same tasks. An interesting note about this quote, it is named ``Greenspun's Tenth Rule'' despite being the only rule in the set\cite{philip_greenspun}.

The next section will explore syntax in an attempt to understand the language better. On a general level, the syntax and style is the same between the Lisp dialects from a programming stand point, so many points may apply to more than just Common Lisp. 

%----------------------------------------------------------------------
\subsection{Syntax}\label{sec:syntax}

Lisp understandably appears foreign to many programmers coming from a curly-brace background. An easy way to understand the syntax for these programmers is to compare Lisp source code with a more common language like C. The following snippets are the C and Lisp version of the Hello World program.

\begin{figure}[H]
\lstinputlisting[language=C]{data/hello.c}
\caption{hello.c}
\label{fig:hello.c}
\end{figure}

\begin{figure}[H]
\lstinputlisting{data/hello.lsp}
\caption{hello.lsp}
\label{fig:hello.lsp}
\end{figure}

In Lisp, parenthesis form lists, which are composed of parts called atoms. The first atom of a list is also a function or a macro that gets applied to the rest of the atoms \cite {successful_lisp_syntax}. In \texttt{hello.lsp} the \texttt{defun} macro is used to define the function \texttt{main}. Inside of \texttt{main} the \texttt{format} function is used to print a string to the terminal, which is specified by the \texttt{t} argument. \texttt{format} behaves much like \texttt{printf}, though it was apparently inspired by Fortran's \texttt{format} function\cite{successful_lisp_format}. hello.lsp defines a main method, but that is optional. It could have just as easily been \texttt{(format t "Hello World")}. 

A list can be defined in the same fashion as the application itself (which is a list to the Lisp interpreter). Creating a list and setting it to a variable would look like the following.

\begin{lstlisting}
(set `var `(1 2 3 ("fish" "dogs") 4))
\end{lstlisting}

Here a two dimentional list is created and assigned to a variable \texttt{var}. The apostrophe that appears before the variable name and the list tells Lisp that these lists should not be evaluated. If they were absent then \texttt{var} is assumed to be an existing variable and the number 1 is assumed to be the name of a function, with the rest of the list being arguments. The apostrophe was required so often that Common Lisp included a \texttt{setq} function that automatically quotes the first argument\cite{successful_lisp_macros}.

\begin{lstlisting}
(setq var `(1 2 3 ("fish" "dogs") 4))
\end{lstlisting}

Everything in Lisp follows this simple, elegant syntax. At more complex levels the parenthesis can seem overwhelming but most IDEs will help with matching and closing pairs of parenthesis.

A logical step after writing a program is to run it. The next section will discuss options that programmers have when running their Lisp applications.  

%----------------------------------------------------------------------
\subsection{Running a Lisp application}\label{sec:run}

As expected, Lisp is very flexible when it comes to running an application. It can be interpreted like a Python program, converted into bytecode like a Java program, or compiled into native machine code like a C program. Tools for all three options exist to aid programmers as well. 

The Superier Lisp Interaction Mode for Emacs (SLIME) is a great tool to get started interpreting Lisp code\cite{slime}. SLIME can take Lisp expressions and evaluate them on the spot, or it can take a Lisp source file. This should feel familiar to anyone who has ever used the Python interpreter. In the case of figure \ref{fig:hello.lsp}, hello.lsp, the file would have to be loaded inside of SLIME and then a function called.

\begin{figure}[H]
\begin{lstlisting}
CL-USER> (load "hello.lsp")
CL-USER> (main)
Hello World
NIL
\end{lstlisting}
\caption{hello.lsp interpreted}
\label{fig:helloInterpreted}
\end{figure}

After main is called, the function is run (displaying ``Hello World") and the return value is presented. Nothing was returned in \texttt{main} so \texttt{NIL} (Lisp's version of \texttt{NULL}) was printed. It is important to note that in Common Lisp, \texttt{NIL} represents the empty list, as well as the boolean value ``false''\cite{common_lisp_intro}.

This is a very convenient way to test Lisp applications and is fully integrated with Emacs, arguably the best IDE for Lisp development. However, the interpreter is not a good solution for code distribution. This is where compilation comes in handy. 

Steel Bank Common Lisp (SBCL) can be used to compile Lisp code into an executable. SBCL is also an interpreter and the compilation process is probably not what most people expect, but it gets the job done. The following snippet will show how to compile hello.lsp from within an SBCL session.

\begin{figure}[H]
\begin{lstlisting}
* (load "hello.lsp")
T
* (sb-ext:save-lisp-and-die "binName" :executable t :toplevel `main)
[undoing binding stack and other enclosing state... done]
[saving current Lisp image into lispbin:
writing 6176 bytes from the read-only space at 0x20000000
writing 4064 bytes from the static space at 0x20100000
writing 44687360 bytes from the dynamic space at 0x1000000000
\end{lstlisting}
\caption{hello.lsp compiled}
\label{fig:helloCompiled}
\end{figure}

Notice how the toplevel function argument needs to be preceeded by an apostrophe; the Lisp syntax holds in all parts of the interpreter.

This will result in the creation of a binary named ``binName'' that can be run like any other executable, and like any other executable, it will work only on the system it was compiled for. If a more cross platform solution is desired then the Common Lisp Compiler (clisp) could be used to compile into an intermediate, platform independent bytecode, similar to how Java works. To compile hello.lsp into bytecode, the following can be executed from the command line.\\

\begin{enumerate}
\item[] \ttfamily\$ clisp -c hello.lsp\\
\end{enumerate}

This will produce a file called ``hello.fas'' which can be loaded in an interpretation session within clisp just like any other lisp file.

%%----------------------------------------------------------------------
%% SECTION IV: Criticisms
%%----------------------------------------------------------------------
%\section{Criticisms}\label{criticism}
%
%Common Lisp criticisms are often times misconceptions or style preferences. David Lamkins summarizes some common objects to the language\cite{successful_lisp_why}.
%
%\subsection{Lisp is slow}
%
%The short answer here is that there should be no significant difference between a Lisp application and a C application assuming the Lisp application is coded properly and compiled instead of interpreted. As mentioned in section \ref{sec:commonlisp}, Common Lisp provides built in methods to tune the efficiency of an application.
%
%\subsection{No one uses Lisp}
%
%
%
%\subsection{Lisp does not support GUIs}
%
%\subsection{Lisp connot be extended with other languages}
%
%\subsection{Lisp's garbage collection is unpredictable}
%
%\subsection{Lisp is only useful in AI}
%
%Two examples of non AI applications that use Lisp are Emacs and AutoCAD. Lisp happens to lend itself well to artificial intelligence because it is good at solving vague problems that require experimentation.  

%----------------------------------------------------------------------
% SECTION V: Conclusion
%----------------------------------------------------------------------
\section{Conclusion}\label{sec:conclusion}

Common Lisp is here to stay. Common criticisms of the language indicate that non Lisp programmers are accustomed to Algol family style syntax and find Lisp a pain to learn, but the language's influence cannot be denied. You may be asking yourself, ``Why would I program in Lisp?", and an appropriate response would be ``Why would you program in any language?". Anyone who believes that one language is enough to solve any problem most likely is not interested in enriching their programming knowledge and experience, so any languge besides their favorite language will not be well received. However, if you truly want to learn to think differently about problem solving in general then there could be no better place to start than Lisp. For example, one of Lisp's strong suites is the ability to get more done with less code. The following snippet was taken from 99-bottles-of-beer.net and show cases this ability\cite{beer}.

\begin{figure}[H]
\begin{lstlisting}
(labels ((foo (x)
   (and (<= 0 x) (cons x (foo (1- x))))))
   (format t (format nil 
        "~~{~~&~~@(~~%~~R ~A ~A!~~)~~:*~~&~~@(~~R~0@*~A!~~)~~&~~@(~2@*~A!~~)~~&~~@(~~[~A~~:;~~:*~~R~~:*~~] ~0@*~A!~~)~~}"
	    "bottles of beer"
	    "on the wall"
	    "take one down, pass it around"	
	    "no more"
	    )
 (foo 99)))
\end{lstlisting}
\caption{99 bottles of beer}
\label{fig:helloCompiled}
\end{figure}

This may not be the most readable code to a new Lisp programmer, but compared with other languages, like C++, it manages to accomplish more with less lines. Hopefully the curious minded will be interested in a new experience.

%----------------------------------------------------------------------
\newpage
\begin{thebibliography}{1}
\bibliographystyle{IEEEbib}
\bibliography{bibliography}
\end{thebibliography}


\end{document}









